import org.w3c.dom.html.HTMLParamElement;

import java.util.Arrays;

/**
 * Created by L.jp
 * Description:
 * User: 86189
 * Date: 2022-05-29
 * Time: 23:19
 */
public class Main {
    public static void main (String[] args) {
        int[] arr = {1,2,6,3,65,23,21,24,15};
        int[] tmp=new int[arr.length];
        mergeSort(arr,0,arr.length-1,tmp);
        System.out.println( Arrays.toString( arr ) );
    }
    public static void mergeSort (int[] arr , int start , int end , int[] tmp) {
        if(start>=end){
            return;
        }
        int mid=(start+end)/2;
        mergeSort( arr,start,mid,tmp );
        mergeSort( arr,mid+1,end,tmp );
        merge(arr,start,end,mid,tmp);
    }
    public static void merge (int[] arr , int start , int end , int mid , int[] tmp){
        int leftIndex=start;
        int rightIndex=mid+1;
        int index=start;
        while ( leftIndex<=mid && rightIndex<=end ){
            if(arr[leftIndex]<arr[rightIndex]){
                tmp[index++]=arr[leftIndex++];
            }else{
                tmp[index++]=arr[rightIndex++];
            }
        }
        while ( leftIndex<=mid ){
            tmp[index++]=arr[leftIndex++];
        }
        while (rightIndex <= end) {
            tmp[index++] = arr[rightIndex++];
        }
        //不能把整个tmp数组赋值给他，每次都是赋值合并好的，每次合并好的区间不一样,但都是从start到end
        for(int i=start;i<=end;i++){
            arr[i] =tmp[i];
        }
    }
}
